1. Field of the Invention
This invention relates generally to memory interfaces, and more particularly to a reactive placement controller for ordering and inserting data transfer commands for banked memory storage.
2. Description of the Related Art
Many memory devices are designed to have a banking nature in order to increase the density of the memory. Unfortunately, the banking nature of the memory devices requires additional cycles to perform setup operations for memory access operations. For example, FIG. 1 is a schematic diagram showing a prior art dynamic random access memory (DRAM) 100. The exemplary DRAM 100 includes a plurality of memory banks 102a-102d, each associated with a page holder 104a-104d. 
Each memory bank 102a-102d is divided into a plurality of pages 108a-108b of data. For example, a particular DRAM could store 32 megabits of data in each memory bank 102a-102d. In this case, each memory bank 102a-102d stores about four thousand pages 108a-108b, with each page 108a-108b having about four thousand bits of data.
The DRAM 100 is a very dense memory array, however data access to the DRAM 100 can be slow because of the setup time required to access the memory banks 102a-102d. For example, to access stored data, a request is made for a particular page within a particular memory bank. This request typically takes the form of a row address corresponding to the selected page, and a bank address corresponding to the selected bank. For example, a read request can be received for data stored in page 108a of memory bank 102a. In response, page 108a is transferred to the page holder 104a, which is associated with memory bank 102a. To access particular data within the selected page 108a, a column address is provided that points to the desired data. Each column address points to a segment of data within the selected page that is the width of the DRAM. For example, if the output 106 of the DRAM 100 is sixteen bits, each column address points to sixteen bits of data within the page 108a stored in the page holder 104a. Increased efficiency is obtained by associating a page holder 104a-104d with each memory bank 102a-102d, allowing each memory bank 102a-102d to operate independently.
In a DRAM, such as illustrated in FIG. 1, the worst efficiency occurs when two memory access operations are received for different pages in the same memory bank, as illustrated next in FIG. 2A. FIG. 2A is a timing diagram illustrating a prior art DRAM access of two different pages in the same memory bank. In a first clock cycle 1, the DRAM receives a request for data located on page 108a of memory bank 102a. In this example it is assume four cycles are required to transfer the requested page from the memory bank to the associated page holder. Thus, in clock cycle 5 a read request can be processed for page holder 104a, which is associated with memory bank 102a and currently stores page 108a. Here, sixty-four bits of data are requested requiring four cycles to complete.
The process of pushing a page from a memory bank to a page holder erases the page data from the memory bank. Hence, when a second page is to be pushed into the same page holder, the first page must be stored back into the memory bank if the data is to be retained. This is referred to as a precharge or refresh. Hence, after the requested data is read, page 108a is stored back into memory bank 102a requiring, in this example, two additional clock cycles. Thereafter, on cycle 12, the request for data located on page 108a′ of memory bank 102a can begin processing.
After twelve clock cycles only four sixteen-bit data chunks have been received, which is unacceptable for many systems. To decrease this latency, systems have been developed to “look ahead” in the data stream to more efficiently send requests to the banked memory device. FIG. 2B is a timing diagram illustrating a prior art DRAM access of two different pages in the same memory bank wherein an additional memory access command is inserted to increase data access efficiency. In the example of FIG. 2B, the memory interface has determined that a third request for a page located in memory bank 102b has been received. Since memory banks 102a and 102b can operate independently, memory access can be improved by processing both data requests together. Thus, the request for page 108b in memory bank 102b is inserted in clock cycle 2. As above, it is assume four cycles are required to transfer page 108b from the memory bank 102b to the associated page holder 104b. Although the requested data is available on clock cycle 6, the DRAM output is being utilized in that clock cycle to output the data from page 108a. Thus, the output for page 108b begins after the data for page 108a is read, in clock cycle 10. Now, after twelve clock cycles seven sixteen-bit data chunks have been output from the DRAM, which is improved from FIG. 2A.
FIG. 3 is a schematic diagram showing an exemplary prior art DRAM controller 300 for reordering memory access commands to increase DRAM efficiency. The DRAM controller 300 includes a command input 302, a plurality of queue entries 304 coupled to a multiplexer 308, and a queue control 306 that provides control signals to the multiplexer 308. The multiplexer 308 also is coupled to a read/write control 312, which provides data to a command control 314. In addition, the queue control 306 is coupled to a bank control 310 that also provides data to the command control 314.
As illustrated in FIG. 3, most queues for DRAM controllers are based on a standard circular queue with separate bank control module. In the DRAM controller 300, the queue entries 304 only contain data for an individual command such as address, length, and read/write flag. The queue control module 306 has a direct connection to each queue entry 304 to determine which queue entry data to send to the read/write control module 312. The queue control module 306 selects which command to execute and tells the bank control module 310 to prepare the bank. When the bank is prepared queue control 306 selects the command to be sent to the read/write control module 312.
Unfortunately, the DRAM bank control presents a major problem in the prior art DRAM controller 300. As illustrated in FIG. 2B, commands to the memory to set up banks need to be ahead of the read/write command by a number of cycles. Because of this, the jobs of the queue control 306 and bank control 310 processes are difficult. A command needs to be selected a long time in advance in order to have the bank control module 310 address the bank to the correct address. When the number of banks in the system increases because of the controller 300 is configured for multiple ranks, the problem of bank control goes up exponentially.
The difficulty with the DRAM controller 300 is that as the number of queue entries 304 is expanded the multiplexer 308 to select the number of queue entries 304 also grows. This problem is increased also due to the fact that the multiplexer 308 is muxing a very large number of bits. The address, length, and read/write flag alone typically is about 40 bits. For example, if the number of queue entries 304 is sixteen, the total number of bits to mux is 16*40=640 bits. This large number of bits presents a problem in synthesis. Furthermore, the queue control module 306 adds additional time to the selection process because of the complex task the queue control module 306 performs. That is, selecting the correct command based on the command type and bank status and priority. The timing for the queue control module 306 also increases as the number of queue entries 304 increases.
In view of the foregoing, there is a need for a DRAM controller for ordering and inserting data transfer commands for banked memory storage that avoids exponential increases in complexity as the “look ahead” functionality increases. The DRAM controller should allow a linear progression of complexity as the number of queue entries increases instead of an exponential increase as is experienced in the prior art.